package cn.genmer.test.security.algorithm.sort;

import java.util.Arrays;

/**
 * 基数排序 思想： 多次计数排序
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {3, 0, 1, 2, 4};
        sort(arr);
        SortUtil.printArray(arr);
    }

    /**
     * 基数排序
     * @param arr
     */
    public static void sort(int[] arr){
        int[] result = new int[arr.length];
        int[] rangeArray = new int[10];

        // 找到最大位数,决定循环次数
        int maxDigit = findMaxDigit(arr);
        // 循环maxDigit次
        for (int i = 0; i < maxDigit; i++) {
            int division = (int)Math.pow(10, i);
            for (int j = 0; j < arr.length; j++) {
                int num = arr[j]/division % 10;
                rangeArray[num]++;
            }

            for (int k = 1; k < rangeArray.length; k++) {
                rangeArray[k] = rangeArray[k-1] + rangeArray[k];
            }

            for (int n = arr.length-1; n >=0; n--) {
                int num = arr[n]/division % 10;
                result[--rangeArray[num]] = arr[n];
            }
//            arr = Arrays.copyOfRange(result, 0, result.length);
            System.arraycopy(result, 0, arr,0, result.length);
            Arrays.fill(rangeArray, 0);
        }
    }

    /**
     * 2022.12.07 首次
     * 2022.12.08 通过
     */
    public static void sortTEST(int[] arr){
        int[] result = new int[arr.length];
        int[] rangeArray = new int[10];

        int maxDigit = findMaxDigit(arr);
        for (int i = 0; i < maxDigit; i++) {
            int division = (int) Math.pow(10, i);
            for (int j = 0; j < arr.length; j++) {
                int num = arr[j]/division % 10;
                rangeArray[num]++;
            }
            for (int k=1; k<rangeArray.length; k++){
                rangeArray[k] = rangeArray[k-1] + rangeArray[k];
            }
            for (int n=arr.length-1; n >= 0; n--){
                int num = arr[n]/division % 10;
                result[--rangeArray[num]] = arr[n];
            }
//            System.arraycopy(result, 0, arr, 0, result.length);
            arr = Arrays.copyOfRange(result, 0, result.length);
            System.out.println("inner arr2" + Arrays.toString(arr));
            Arrays.fill(rangeArray, 0);
        }
    }


    private static int findMaxDigit(int[] arr){
        int maxNum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxNum) maxNum = arr[i];
        }
        return String.valueOf(maxNum).length();
    }
}
